package server.simple100;


import org.junit.Test;

/**
 * 141. 环形链表
 */
public class LeetCode141 {


	@Test
	public void test() {
//		ListNode head3 = new ListNode(1);
//		ListNode head4 = new ListNode(2);
//		head3.next = head4;

		ListNode head3 = new ListNode(3);
		ListNode head2 = new ListNode(2);
		ListNode head0 = new ListNode(0);
		ListNode head4 = new ListNode(-4);
		head3.next = head2;
		head2.next = head0;
		head0.next = head4;
		head4.next = head2;
		System.out.println(hasCycle(head3));
	}

	/**
	 * @param head
	 * @return boolean
	 * @author wangsong
	 * @date 2022/4/7 13:56
	 */
	public boolean hasCycle(ListNode head) {
		// 双指针( 1-每次向前走一步  2-每次像前走两步  当2走到结尾在往回追到1时，代表是环形链表)
		ListNode z1 = head;
		ListNode z2 = head;
		while (z1 != null && z2 != null && z2.next != null) {
			z1 = z1.next;
			z2 = z2.next.next;
			if (z1 == z2) {
				return true;
			}
		}
		return false;
	}

	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}
}
